﻿#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <chrono>
#include <random>

using namespace std;

using value = int;

using key1 = std::pair<int, int>;
using key2 = int;
using key3 = std::pair<int, int>;
using key4 = int;

using map1 = std::map<key1, value>;
using map2 = std::map<key2, value>;

struct pair_hasher
{
    template <class First, class Second>
    std::size_t operator()(const std::pair<First, Second> &p) const
    {
        auto h1 = std::hash<First>{}(p.first);
        auto h2 = std::hash<Second>{}(p.second);
        return h1 ^ h2;
    }
};

using map3 = std::unordered_map<key3, value, pair_hasher>;

using map4 = std::unordered_map<key4, value>;

key1 makeKey1(int i, int j)
{
    return std::make_pair(i, j);
}

key2 makeKey2(int i, int j)
{
    return i * 10000000 + j;
}

key3 makeKey3(int i, int j)
{
    return std::make_pair(i, j);
}

key4 makeKey4(int i, int j)
{
    return makeKey2(i, j);
}

std::mt19937 rng;
std::uniform_int_distribution<std::mt19937::result_type> dist(0, 1000);

void init()
{
    rng.seed(std::random_device()());
}

int roll()
{
    return dist(rng);
}

#define RUN(i)                                                                                                                                                   \
    {                                                                                                                                                            \
        auto begin = std::chrono::steady_clock::now();                                                                                                           \
        for (auto n : ns)                                                                                                                                        \
        {                                                                                                                                                        \
            auto key = makeKey##i(n, 1);                                                                                                                         \
            auto it = m##i.find(key);                                                                                                                            \
            if (it == m##i.end())                                                                                                                                \
            {                                                                                                                                                    \
                cout << n << " no in m" << i << endl;                                                                                                            \
            }                                                                                                                                                    \
        }                                                                                                                                                        \
        cout << "m" << i << " use: " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - begin).count() << "ms" << endl; \
    }

int main(int argc, char *argv[])
{
    init();

    map1 m1;
    map2 m2;
    map3 m3;
    map4 m4;

    for (int i = 0; i < 10001; ++i)
    {
        m1.emplace(makeKey1(i, 1), i);
        m2.emplace(makeKey2(i, 1), i);
        m3.emplace(makeKey3(i, 1), i);
        m4.emplace(makeKey4(i, 1), i);
    }

    std::vector<int> ns;
    for (int i = 0; i < 100000000; ++i)
    {
        ns.push_back(roll());
    }

    cout << "begin" << endl;

    RUN(1);

    RUN(2);

    RUN(3);

    RUN(4);

    cout << "end" << endl;

    return 0;
}
